package com.jacklei.ch14;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/*
* 给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。

请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。

请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。

回文串 指的是从前往后和从后往前读一样的字符串。

 

示例 1：

输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。
示例 2：

输入：words = ["ab","ty","yt","lc","cl","ab"]
输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。
示例 3：

输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。
 

提示：

1 <= words.length <= 105
words[i].length == 2
words[i] 仅包含小写英文字母。
通过次数6,143提交次数15,195

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindrome-by-concatenating-two-letter-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class longestPalindromeByConcatenatingTwoLetterWords {
    public static void main(String[] args) {
        longestPalindromeByConcatenatingTwoLetterWords l = new longestPalindromeByConcatenatingTwoLetterWords();
        System.out.println(l.longestPalindrome(new String[]{
                "ab","ty","yt","lc","cl","ab"
        }));
    }//["ab","ty","yt","lc","cl","ab"]
    public int longestPalindrome(String[] words) {
        int ans = 0;
        HashMap<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.containsKey(word)){
                map.put(word,map.get(word)+1);
            }else {
                map.put(word,1);
            }
        }
        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
        boolean flat = false;
        while (iterator.hasNext()){
            Map.Entry<String, Integer> next = iterator.next();
            String key = next.getKey();
            StringBuffer reverse = new StringBuffer(key).reverse();
            if(key.equals(reverse.toString())) {
                //两个字符相同
                Integer integer = map.get(key);
                if (integer % 2 == 1){
                    //只有一个
                    flat = true;//打标记
                }
                ans += (integer/2 * 4);
            } else if(map.containsKey(reverse.toString())){
                //两个字符不相同
               int temp = Math.min(map.get(key),map.get(reverse.toString()));
               ans += (temp *2);
            }

        }
        return flat ? ans + 2 : ans;
    }

}

